import collections


class Solution:
    def findLadders(self, beginWord: str, endWord: str,
                    wordList: list) -> list:
        wordList = set(wordList)
        if endWord not in wordList:
            return []
        laryer = {}
        laryer[beginWord] = [[beginWord]]
        while laryer:
            newLaryer = collections.defaultdict(list)
            for word in laryer.keys():
                if word == endWord:
                    return laryer[endWord]
                else:
                    for i in range(len(word)):
                        for s in 'abcdefghijklmnopqrstuvwxyz':
                            newWord = word[:i] + s + word[i + 1:]
                            if newWord in wordList:
                                newLaryer[newWord] += [
                                    path + [newWord] for path in laryer[word]
                                ]
            for key in newLaryer.keys():
                wordList.remove(key)
            laryer = newLaryer
        return []
